/*
 * @lc app=leetcode.cn id=1024 lang=javascript
 *
 * [1024] 视频拼接
 */

// @lc code=start
/**
 * @param {number[][]} clips
 * @param {number} T 片段的总长度
 * @return {number}
 */
var videoStitching = function (clips, T) {
  const maxLimit = new Array(T).fill(0);
  let result = 0,
    prev = 0,
    last = 0;

  for (let [m, n] of clips) {
    if (m < T) {
      maxLimit[m] = Math.max(maxLimit[m], n);
    }
  }

  for (let i = 0; i < T; i++) {
    last = Math.max(last, maxLimit[i]);

    if (i === last) {
      return -1;
    }

    if (i === prev) {
      result++;
      prev = last;
    }
  }

  return result;
};
// @lc code=end

/**
 * 时间复杂度：O(T+N)，其中 T 是区间的长度，N 是子区间的数量。们需要枚举每一个位置，时间复杂度 O(T)，同时我们还需要预处理所有的子区间，时间复杂度 O(N)
 * 空间复杂度：O(T)，其中 T 是区间的长度。对于每一个位置，我们需要记录以其为左端点的子区间的最右端点
 */
